// Copyright 2011 Jefferson Willian
// willmont7@gmail.com

/* Quick-Find Algorithm                  */
/* O(1) para verificar conectividiade    */
/* O(n) para conectar dois pontos        */

class quickFind {
  private:
    int *id;
    int N;

  public:
    explicit quickFind(int n);
    bool connected(int v1, int v2);
    bool make(int v1, int v2);
};

quickFind::quickFind(int n) {
  N = n;
  id = new int[N];

  for (int i = 0;i < N;i++)
    id[i] = i;
}

/* Verifica se dois pontos de um grafo estao conectados indiretamente */
bool quickFind::connected(int v1, int v2) {
  return id[v1] == id[v2];
}

/* Conecta dois pontos do grafo indiretamente */
bool quickFind::make(int v1, int v2) {
  int t = id[v1];

  if (t == id[v2])
    return false;

  /* Para todas conexoes com 'v1' faz agora conexao com 'v2' */
  for (int i = 0;i < N;i++)
    if (id[i] == t)
      id[i] = id[v2];

  return true;
}

//----------------------------------------------------------------//

/* Quick-Union Algorithm                 */
/* O(logn)* para conectar dois pontos    */
/* O(logn)* para verificar conectividade */
/* *pior caso                            */

class quickUnion {
  private:
    int *id;
    int *depth;

  public:
    explicit quickUnion(int N);
    bool connected(int v1, int v2);
    bool make(int v1, int v2);
};

quickUnion::quickUnion(int N) {
  id = new int[N];
  depth = new int[N];

  for (int i = 0;i < N;i++) {
    id[i] = i;
    depth[i] = 1;
  }
}

/* Verifica se dois pontos de um grafo estao conectados indiretamente */
bool quickUnion::connected(int v1, int v2) {
  int i, j;
  /* Pega vertice raiz da ligacao do ponto 'v1' */
  for (i = v1;i != id[i]; i = id[i]);
  /* Pega vertice raiz da ligacao do ponto 'v2' */
  for (j = v2;j != id[j]; j = id[j]);
  return (i == j);
}

/* Conecta dois pontos do grafo indiretamente */
bool quickUnion::make(int v1, int v2) {
  int i, j;
  /* Pega vertice raiz da ligacao do ponto 'v1' */
  for (i = v1;i != id[i]; i = id[i]);
  /* Pega vertice raiz da ligacao do ponto 'v2' */
  for (j = v2;j != id[j]; j = id[j]);
  if (i == j) return false;
  /* Conecta a menor arvore na maior */
  if (depth[i] < depth[j]) {
    id[i] = j;
    depth[j] += depth[i];
  } else {
    id[j] = i;
    depth[i] += depth[j];
  }
  return true;
}